package com.LeetCodeT.Greedy;
// -*- coding: utf-8 -*-

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;

/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-04 00:15
 * IDE: IntelliJ IDEA
 * Introduction:
 */
public class FindMinArrowShots {
    /**
     * 求射爆气球所需要的最小弓箭数 ->求数组之间的最大交集
     */
    public int findMinArrowShots(int[][] points) {
        // 动态缩小-> 范围缩小 -> 确定两个集合的最大交集
        // 将集合排好序在进行探索
        /*
         * 特殊情况： 一个数组两边都存在交集，但是交集和交集之间并没有交集
         * 目的：使用尽可能少的箭射爆尽可能多的气球
         * 使用map存储区间信息（区间可以缩小但是不可以扩大：保证了同一区间的气球都可以射爆）
         * 特殊情况时候：区间分割
         * 关键在于区域的定位和缩小
         *
         * */

        //1 实现对二维数组的排序
       /* Arrays.sort(points, new Comparator<int[]>() {
            @Override
            *//**
         * 重写比较方法，实现二维数组根据区间起点升序排序
         *//*
            public int compare(int[] x, int[] y) {
                return x[0] - y[0];  x[0]<y[0]?-1:(x[0]==y[0]?0:1);
            }
        });*/
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        //使用HashMap实现对集合区域的表示
        HashMap<Integer, Integer> ans = new HashMap<>(0);
        int n = points.length;
        int[] keySet = new int[n];
        for (int i = 0; i < n; i++) {
            // 获取每一个区域的起点，方便后面进行遍历
            int[] point = points[i];
            keySet[i] = point[0];
            boolean flag = false;
            // 如何实现对区域的定位和比较-> 使用keySet遍历
            int tmp = i;
            for (; tmp >= 0; --tmp) {
                // 从高往低找->区域起点肯定变小
                int j = keySet[tmp];
                if (ans.containsKey(j) && ans.get(j) >= point[0]) {
                    // 区域的缩小->需要对区域的左右值进行保证->  左>右
                    // 区域左边可以存在负数，区域的起点肯定是集合中某个区域的起点—> 缩小遍历范围
                    ans.put(point[0], Math.min(ans.get(j), point[1]));
                    if (point[0] != j) {
                        // 避免当区域相同的时候造成误删
                        ans.remove(j);
                    }
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                // 区域不存在
                ans.put(point[0], point[1]);
                flag = false;
            }
        }
        return ans.size();
    }

    @Test
    public void shout() {
        //int[][] points = {{-1, 1}, {0, 1}, {2, 3}, {1, 2}};
        int[][] points = {{-2147483646, -2147483645}, {2147483646, 2147483647}};
//        int k1 = points[0][0];
//        int k2 = points[1][0];
//        System.out.println(" k1 = " + k1 + ",k2 = " + k2);
//        if (k1 > k2) {
//            System.out.println("k1>k2");
//        } else {
//            System.out.println("k1<k2");
//        }
//        System.out.println("----------------");
//        System.out.println("k1 - k2 = " + (k1 - k2));
//        System.out.println("----------------");
//        System.out.println(Integer.MAX_VALUE);
//        System.out.println("----------------");
//        System.out.println(-4294967292);
        System.out.println(findMinArrowShots(points));
    }
}
